package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {39,4,564,345,667,3,45,6,67,8,34,5,1,41};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void mergeSort(int[] arr){
        if(arr==null||arr.length<=1) return;
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }
    public static void mergeSort(int[] arr,int left,int right,int[]temp){
        if(left<right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i<=mid&&j<=right){
            if(arr[i]>arr[j]) temp[k++] = arr[j++];
            else temp[k++] = arr[i++];
        }
        while(i<=mid){
            temp[k++]=arr[i++];
        }
        while(j<=right){
            temp[k++]=arr[j++];
        }
        System.arraycopy(temp,0,arr,left,k);
    }

}
